package 回溯算法;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * @Author: biubiu0002
 * @Date: 2021-03-31 19:19
 **/
public class 子集Ⅱ {
    List<List<Integer>> res = new LinkedList<>();

    public List<List<Integer>> subsetsWithDup(int[] nums) {
        LinkedList<Integer> trace = new LinkedList<>();
        Arrays.sort(nums);

        backtrace(nums,trace,0);
        return res;


    }

    //basecase
    //选择列表
    //路径
    void backtrace(int[] nums,LinkedList<Integer> trace,int index){
        //basecase

        //先序遍历
        if(!res.contains(trace))
            res.add(new LinkedList<>(trace));
        //选择列表
        for(int i=index;i<nums.length;i++){
            trace.add(nums[index]);
            //做选择
            backtrace(nums,trace,i+1);
            //撤销选择
            trace.removeLast();


        }


    }
}
